home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / parser / norml.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  8.0 KB  |  443 lines
  1. # include    <ingres.h>
  2. # include    <aux.h>
  3. # include    <tree.h>
  4. # include    <symbol.h>
  5. # include    <sccs.h>
  6.  
  7. SCCSID(@(#)norml.c    8.1    12/31/84)
  8.  
  9. /*
  10. **  NORML.C -- functions for normalizing tree
  11. **
  12. **    Defines
  13. **        norml -- main routine
  14. **        norm
  15. **        travers
  16. **        nnorm
  17. **        notpush
  18. **        adjust
  19. **        treedup
  20. **        mvands
  21. **
  22. **    Trace Flags:
  23. **        NORMAL.C ~~ 56, 57
  24. */
  25.  
  26. /*
  27. **  NORML -- normalizing routine
  28. **
  29. **    this routine passes the qualification clause portion of the query
  30. **    tree to the routines for depressing nots and for conjunctive 
  31. **    normalization.  It also calls a routine to place an and with one
  32. **    null branch at the rightmost end of the tree.
  33. **
  34. **    Parameters:
  35. **        ptr -- tree to normalize
  36. **
  37. **    Returns:
  38. **        nothing
  39. **
  40. **    Trace Flags:
  41. **        norml ~~ 56.0
  42. */
  43.  
  44. QTREE *
  45. norml(ptr)
  46. QTREE    *ptr;
  47. {
  48.     extern QTREE    *nnorm();
  49.     extern QTREE    *travers();
  50.     extern QTREE    *tree();
  51.     extern char    Qbuf[];
  52.  
  53. # ifdef    xPTR1
  54.     tTfp(56, 0, "norml(%d)\n", ptr);
  55. # endif
  56.  
  57.     if (ptr == NULL)
  58.         return (tree(NULL, NULL, QLEND, 0, 0));
  59.  
  60.     /* push through the 'nots' as far a possible */
  61.     ptr = nnorm(ptr);
  62.  
  63.     /* make tree into conjunctive normal form */
  64.     ptr = travers(ptr);
  65.  
  66.     /* terminate the list on the rightmost branch */
  67.     adjust(&ptr);
  68.  
  69.     /* make 'ands' into a linear list */
  70.     mvands(ptr);
  71.  
  72. # ifdef    xPTR1
  73.     tTfp(56, 1, ">>norml(%d)\n", ptr);
  74. # endif
  75.  
  76.     return (ptr);
  77. }
  78.  
  79.  
  80. /*
  81. ** NORM
  82. **    this routine takes a tree which has nots only at the lower ends, and
  83. **    places it into conjunctive normal form by repeatedly applying the
  84. **    replacement rule: A or (B and C) ==> (A or B) and (A or C)
  85. **
  86. **    Trace Flags:
  87. **        norm ~~ 56.4
  88. */
  89.  
  90. QTREE *
  91. norm(p)
  92. register QTREE        *p;
  93. {
  94.     register QTREE        *lptr;
  95.     register QTREE        *rptr;
  96.     extern QTREE        *treedup();
  97.     extern QTREE        *tree();
  98.  
  99. # ifdef    xPTR1
  100.     tTfp(56, 4, "norm(%d)\n", p);
  101. # endif
  102.  
  103.     switch (p->sym.type)
  104.     {
  105.       case AND:
  106.         p->left = norm(p->left);
  107.         p->right = norm(p->right);
  108.         break;
  109.  
  110.       case OR:
  111.         if (p->right->sym.type == AND)
  112.         {
  113.         andright:
  114.             /*
  115.             ** combine left subtree with each subtree of the
  116.             ** right subtree
  117.             */
  118.             /*
  119.             ** use copy first so that the copy is guaranteed to be
  120.             ** the same as the original
  121.             */
  122.             lptr = tree(treedup(p->left), p->right->left, OR, sizeof(struct rootnode) - 2, 0);
  123.             rptr = tree(p->left, p->right->right, OR, sizeof(struct rootnode) - 2, 0);
  124.             lptr = norm(lptr);
  125.             rptr = norm(rptr);
  126.             /* change node type to AND from OR */
  127.             p->left = lptr;
  128.             p->right = rptr;
  129.             p->sym.type = AND;    /* length is same */
  130.             break;
  131.         }
  132.         if (p->left->sym.type == AND)
  133.         {
  134.         andleft:
  135.             /*
  136.             ** combine right subtree with each subtree of the
  137.             ** left subtree
  138.             */
  139.             /*
  140.             ** again, the copy should be used first
  141.             */
  142.             lptr = tree(p->left->left, treedup(p->right), OR, sizeof(struct rootnode) - 2, 0);
  143.             rptr = tree(p->left->right, p->right, OR, sizeof(struct rootnode) - 2, 0);
  144.             lptr = norm(lptr);
  145.             rptr = norm(rptr);
  146.             /* change node type to AND from OR */
  147.             p->left = lptr;
  148.             p->right = rptr;
  149.             p->sym.type = AND;
  150.             break;
  151.         }
  152.         /*
  153.         ** when TRAVERS is being used to optomize the normalization
  154.         ** order there should never be (I think) an OR as a child
  155.         ** of the OR in the parent.  Since TRAVERS works bottom up
  156.         ** in the tree the second OR level should be gone.
  157.         */
  158.         if (p->right->sym.type == OR)
  159.         {
  160.             /* skip this (p->sym.type) "or" and normalize the right subtree */
  161.             p->right = norm(p->right);
  162.  
  163.             /* now re-try the current node */
  164.             if (p->right->sym.type == AND)
  165.                 goto andright;
  166.             break;
  167.         }
  168.         if (p->left->sym.type == OR)
  169.         {
  170.             /* skip this "or" and normalize the left subtree */
  171.             p->left = norm(p->left);
  172.  
  173.             /* now re-try the current node */
  174.             if (p->left->sym.type == AND)
  175.                 goto andleft;
  176.             break;
  177.         }
  178.         break;
  179.     }
  180.     return (p);
  181. }
  182.  
  183. /*
  184. ** TRAVERS
  185. **    traverse the tree so that conversion of ORs of ANDs can
  186. **    take place at the innermost clauses first.  IE, normalize
  187. **    before replication rather than after replication.
  188. **
  189. **    This routine need not be used.  The NORM routine will completely
  190. **    traverse the tree and normalize it but...    TRAVERS finds
  191. **    the lowest subtree to normalize first so that sub-trees can
  192. **    be normalized before replication, hence reducing the time required
  193. **    to normalize large trees.  It will also make OR-less trees faster
  194. **    to normalize (since nothing need be done to it).
  195. **
  196. **    Trace Flags:
  197. **        travers ~~ 56.8
  198. */
  199.  
  200. QTREE *
  201. travers(p1)
  202. QTREE    *p1;
  203. {
  204.     register QTREE    *p;
  205.     extern QTREE        *norm();
  206.  
  207. # ifdef    xPTR1
  208.     tTfp(56, 8, "travers(%d)\n", p1);
  209. # endif
  210.  
  211.     p = p1;
  212.     if (p->right != NULL)
  213.         p->right = travers(p->right);
  214.     if (p->left != NULL)
  215.         p->left = travers(p->left);
  216.     if (p->sym.type == OR)
  217.         p = norm(p);
  218.     return (p);
  219. }
  220. /*
  221. ** NNORM
  222. **    this routine depresses nots in the query tree to the lowest possible
  223. **    nodes.  It may also affect arithmetic operators in this procedure
  224. **
  225. **    Trace Flags:
  226. **        nnorm ~~ 56.12
  227. */
  228. QTREE *
  229. nnorm(p1)
  230. QTREE    *p1;
  231. {
  232.     extern QTREE        *notpush();
  233.     register QTREE    *p;
  234.  
  235. # ifdef    xPTR1
  236.     tTfp(56, 12, "nnorm(%d)\n", p1);
  237. # endif
  238.  
  239.     p = p1;
  240.     if (p->sym.type == AGHEAD)
  241.     {
  242.         /*
  243.         ** don't need to continue past an AGHEAD
  244.         ** actually, it causes problems if you do
  245.         ** because the qualification on the agg
  246.         ** has already been normalized and the
  247.         ** QLEND needs to stay put
  248.         */
  249.         return (p);
  250.     }
  251.     if ((p->sym.type == UOP) && (p->sym.value.sym_op.opno == opNOT))
  252.     {
  253.         /* skip not node */
  254.         p = p->right;
  255.         p = notpush(p);
  256.     }
  257.     else
  258.     {
  259.         if (p->left != NULL)
  260.             p->left = nnorm(p->left);
  261.         if (p->right != NULL)
  262.             p->right = nnorm(p->right);
  263.     }
  264.     return (p);
  265. }
  266.  
  267. /*
  268. ** NOTPUSH
  269. **    this routine decides what to do once a not has been found in the
  270. **    query tree
  271. **
  272. **    Trace Flags:
  273. **        notpush ~~ 57.0
  274. */
  275. QTREE *
  276. notpush(p1)
  277. QTREE    *p1;
  278. {
  279.     extern QTREE        *nnorm();
  280.     register QTREE    *p;
  281.  
  282. # ifdef    xPTR1
  283.     tTfp(57, 0, "notpush(%d)\n", p1);
  284. # endif
  285.  
  286.     p = p1;
  287.     switch (p->sym.type)
  288.     {
  289.       case AND:
  290.         p->sym.type = OR;
  291.         p->left = notpush(p->left);
  292.         p->right = notpush(p->right);
  293.         break;
  294.  
  295.       case OR:
  296.         p->sym.type = AND;
  297.         p->left = notpush(p->left);
  298.         p->right = notpush(p->right);
  299.         break;
  300.  
  301.       case BOP:
  302.         switch (p->sym.value.sym_op.opno)
  303.         {
  304.           case opEQ:
  305.             p->sym.value.sym_op.opno = opNE;
  306.             break;
  307.  
  308.           case opNE:
  309.             p->sym.value.sym_op.opno = opEQ;
  310.             break;
  311.  
  312.           case opLT:
  313.             p->sym.value.sym_op.opno = opGE;
  314.             break;
  315.  
  316.           case opGE:
  317.             p->sym.value.sym_op.opno = opLT;
  318.             break;
  319.  
  320.           case opLE:
  321.             p->sym.value.sym_op.opno = opGT;
  322.             break;
  323.  
  324.           case opGT:
  325.             p->sym.value.sym_op.opno = opLE;
  326.             break;
  327.  
  328.           default:
  329.             syserr("strange BOP in notpush '%d'", p->sym.value.sym_op.opno);
  330.         }
  331.         break;
  332.  
  333.       case UOP:
  334.         if (p->sym.value.sym_op.opno == opNOT)
  335.         {
  336.             /* skip not node */
  337.             p = p->right;
  338.             p = nnorm(p);
  339.         }
  340.         else
  341.             syserr("strange UOP in notpush '%d'", p->sym.value.sym_op.opno);
  342.         break;
  343.  
  344.       default:
  345.         syserr("unrecognizable node type in notpush '%d'", p->sym.type);
  346.     }
  347.     return (p);
  348. }
  349.  
  350. /*
  351. ** ADJUST
  352. **    terminate qual with an AND and a QLEND at the rightmost branch
  353. **
  354. **    Trace Flags:
  355. **        adjust ~~ 57.4
  356. */
  357. adjust(pp)
  358. QTREE    **pp;
  359. {
  360.     extern QTREE        *tree();
  361.     register QTREE    *p;
  362.  
  363. # ifdef    xPTR1
  364.     tTfp(57, 4, "adjust(%d)\n", pp);
  365. # endif
  366.  
  367.     p = *pp;
  368.     switch (p->sym.type)
  369.     {
  370.       case AND: 
  371.         adjust(&(p->right));
  372.         break;
  373.  
  374.       case OR:
  375.       default:
  376.         *pp = tree(p, tree(NULL, NULL, QLEND, 0, NULL), AND, sizeof(struct rootnode) - 2, 0);
  377.         break;
  378.     }
  379. }
  380. /*
  381. **  TREEDUP -- 
  382. **
  383. **    Trace Flags:
  384. **        norm ~~ 57.8
  385. */
  386.  
  387.  
  388. QTREE
  389. *treedup(p1)
  390. QTREE    *p1;
  391. {
  392.     register QTREE    *np;
  393.     register QTREE    *p;
  394.     extern char    Qbuf[];
  395.     extern char    *need();
  396.  
  397. # ifdef    xPTR1
  398.     tTfp(57, 8, "treedup(%d)\n", p1);
  399. # endif
  400.  
  401.     if ((p = p1) == NULL)
  402.         return (p);
  403.  
  404.     np = (QTREE *) need(Qbuf, (p->sym.len & I1MASK) + QT_HDR_SIZ);
  405.  
  406.     bmove(p, np, (p->sym.len & I1MASK) + QT_HDR_SIZ);
  407.  
  408.     np->left = treedup(p->left);
  409.     np->right = treedup(p->right);
  410.     return (np);
  411. }
  412.  
  413. /*
  414. **    MVANDS -- pushes all AND's in Qual into linear list
  415. **
  416. **    Trace Flags:
  417. **        mvands ~~ 57.12
  418. */
  419. mvands(andp)
  420. QTREE    *andp;
  421. {
  422.     register QTREE    *ap, *lp, *rp;
  423.  
  424. # ifdef    xPTR1
  425.     tTfp(57, 12, "mvands(%d)\n", andp);
  426. # endif
  427.  
  428.     ap = andp;
  429.     if (ap->sym.type == QLEND)
  430.         return;
  431.     rp = ap->right;
  432.     lp = ap->left;
  433.     if (lp->sym.type == AND)
  434.     {
  435.         ap->left = lp->right;
  436.         ap->right = lp;
  437.         lp->right = rp;
  438.         mvands(ap);
  439.     }
  440.     else
  441.         mvands(rp);
  442. }
  443.